/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)  return NULL;
        /*
        二叉树的镜像就是在遍历过程中交换左右子树
        */
        swapMirrorTree(root);
        return root;
    }

    //使用递归来遍历并交换左右子树
    void swapMirrorTree(TreeNode* root){
        //当前节点左右子树均为空时，递归结束
        if(!root->left && !root->right)  return;
        TreeNode* store = root->left;
        root->left = root->right;
        root->right = store;
        if(root->left)  swapMirrorTree(root->left);
        if(root->right)  swapMirrorTree(root->right);
        return;
    }
};

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)  return NULL;
        /*
        二叉树的镜像就是在遍历过程中交换左右子树
        */
        swapMirrorTree(root);
        return root;
    }

    //使用循环实现(2020/11/26 一刷用循环遍历二叉树)
    //创建一个数组用以保存每次循环需遍历的节点，当所有遍历的节点都是叶节点时，循环结束
    //缺点：如果二叉树很深，将会造成循环过长，内存暴增的问题
    void swapMirrorTree(TreeNode* root){
        TreeNode* pTemp = NULL;
        bool isEntry = false;//记录本次循环是否所有节点均为空节点
        vector<TreeNode*> treeNodeStore;
        int n = 1;  //二叉树的深度
        treeNodeStore.push_back(root);
        int loopStart = 0;
        int loopEnd = 0;
        while(!isEntry){
            isEntry = true;
            loopStart = (int)pow(2,n - 1) - 1;
            loopEnd = (int)pow(2, n) - 1;
            for(int i = loopStart; i < loopEnd; ++i){
                if(!treeNodeStore[i]){
                    treeNodeStore.push_back(NULL);
                    treeNodeStore.push_back(NULL);
                    continue;
                }
                if(treeNodeStore[i]->left || treeNodeStore[i]->right){
                    if(isEntry){
                        isEntry = false;
                    }
                    pTemp = treeNodeStore[i]->left;
                    treeNodeStore[i]->left = treeNodeStore[i]->right;
                    treeNodeStore[i]->right = pTemp;
                }
                //将交换后的左右结点存入数组中
                treeNodeStore.push_back(treeNodeStore[i]->left);
                treeNodeStore.push_back(treeNodeStore[i]->right);
            }
            ++n;
        }
        return;
    }
};

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        /*
        二叉树的镜像就是在遍历过程中交换左右子树
		(使用循环实现对二叉树的遍历)
        模型：使用栈模拟先序遍历模型
        循环操作：交换栈顶节点的左右结点
        循环结束条件：栈为空
        */
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* pNode = st.top();
            st.pop();
            if(!pNode)  continue;
            TreeNode* pTemp = pNode->left;
            pNode->left = pNode->right;
            pNode->right = pTemp;

            st.push(pNode->left);
            st.push(pNode->right);
        }

        return root;
    }
};

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        /*
        二叉树的镜像就是在遍历过程中交换左右子树
        (使用循环实现对二叉树的遍历)
        模型：使用队列模拟二叉树层次遍历
        循环操作：交换队首节点的左右结点
        循环结束条件：队列为空
        */
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* pNode = q.front();
            q.pop();
            if(!pNode)  continue;
            TreeNode* pTemp = pNode->left;
            pNode->left = pNode->right;
            pNode->right = pTemp;

            q.push(pNode->left);
            q.push(pNode->right);
        }

        return root;
    }
};